package demo1;

import java.util.*;

public class Solution {

    public static void main1(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = 3, x = 50;
//        int[] arr = new int[]{50, 105, 200};
//
//        int t = x;
//        for(int i = 0; i < n; i++){
//            int tmp = arr[i];
//            if(t >= tmp){
//                t += tmp;
//            }else{
//                t += func(x, tmp);
//                // System.out.println(func(x, tmp));
//            }
//        }
//         System.out.println(t);

        System.out.println(func(105,200));
    }
    public static int func(int i, int j){
        int min = i > j ? j : i;
        int ret = 1;
        for(int k = 1; k <= min; k++){
            if(i % k == 0 && j % k == 0){
                ret = k;
            }
        }
        return ret;
    }

    public static int maxValue (int[][] grid) {
        // write code here
        int n = grid.length, m = grid[0].length;
        int[][] dp = new int[n + 1][m + 1];

        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        int[][] num = new int[][]{{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(maxValue(num));
    }
}
